package dayPractice.快速幂;

import java.util.Scanner;

/**
 * 3 ^ 1000000
 * <p>
 * 3 ^ 1 = 3
 * 3 ^ 2 = 9
 * 3 ^ 4 = 81
 * 3 ^ 8 =
 * <p>
 * 3 ^ (2 ^ 19)
 *
 * @author Summerday
 */
public class AB {

    // 求 a ^ b mod p
    static int a, b, p;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        p = sc.nextInt();
        long res = 1 % p;
        long k = a;
        while (b != 0) {
            // 对b的每一位数判断
            if ((b & 1) == 1)
                res = res * k % p;
            k = k * k % p;
            b >>= 1;
        }
        System.out.println(res);

    }

}
